package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/search-insert-position/'>搜索插入位置(Search Insert Position)</a>
 * <p>给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。</p>
 * <p>请必须使用时间复杂度为 O(log n) 的算法。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1:
 *      输入: nums = [1,3,5,6], target = 5
 *      输出: 2
 *
 * 示例 2:
 *      输入: nums = [1,3,5,6], target = 2
 *      输出: 1
 *
 * 示例 3:
 *      输入: nums = [1,3,5,6], target = 7
 *      输出: 4
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= nums.length <= 10^4</li>
 *     <li>-10^4 <= nums[i] <= 10^4</li>
 *     <li>nums 为 无重复元素 的 升序 排列数组</li>
 *     <li>-10^4 <= target <= 10^4</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/25 11:53
 */
public class LC0035SearchInsertPosition_S {
    static class Solution {
        public int searchInsert(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                if (nums[mid] > target) {
                    right = mid - 1;
                } else if (nums[mid] < target) {
                    left = mid + 1;
                } else {
                    return mid;
                }
            }
            return left;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.searchInsert(new int[]{1, 3, 5, 6}, 5));
        System.out.println(solution.searchInsert(new int[]{1, 3, 5, 6}, 2));
        System.out.println(solution.searchInsert(new int[]{1, 3, 5, 6}, 7));
        System.out.println(solution.searchInsert(new int[]{1, 3, 5, 6}, 4));
    }
}
